Date: Wed, 08 Jan 1997 20:36:02 GMT
Server: NCSA/1.4.2
Content-type: text/html

<!DOCTYPE HTML PUBLIC "-//W3O//DTD W3 HTML 2.0//EN">
<!Converted with LaTeX2HTML 95 (Thu Jan 19 1995) by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, University of Leeds >
<HEAD>
<TITLE>CSE 322  
Assignment 10 Solution Set  
Friday, March 8, 1996</TITLE>
</HEAD>
<BODY>
<meta name="description" value="CSE 322  
Assignment 10 Solution Set  
Friday, March 8, 1996">
<meta name="keywords" value="hw10soln">
<meta name="resource-type" value="document">
<meta name="distribution" value="global">
<P>
 <BR> <HR><A NAME=tex2html1 HREF="node1.html"><IMG ALIGN=BOTTOM ALT="next" SRC="http://www.cs.washington.edu/general/latex2html_icons//next_motif.gif"></A>   <IMG ALIGN=BOTTOM ALT="up" SRC="http://www.cs.washington.edu/general/latex2html_icons//up_motif_gr.gif">   <IMG ALIGN=BOTTOM ALT="previous" SRC="http://www.cs.washington.edu/general/latex2html_icons//previous_motif_gr.gif">         <BR>
<B> Next:</B> <A NAME=tex2html2 HREF="node1.html">   About this document </A>
<BR> <HR> <P>
<P>
<H1>CSE 322  
Assignment 10 Solution Set  
Friday, March 8, 1996</H1>
<P><STRONG></STRONG><P>
<P><STRONG></STRONG><P>
<P>
<OL><LI>
(Thanks to P. Kromann for the trick on this one)
A DPDA for the given language:  
<br>
<IMG SRC="hw10pda.gif">
<p>
The computation of <b>abbac</b>:
<P><IMG  ALIGN=BOTTOM ALT="" SRC="img1.gif"><P>
<P>
<LI> 
<IMG  ALIGN=MIDDLE ALT="" SRC="img2.gif"> where
<IMG  ALIGN=MIDDLE ALT="" SRC="img3.gif">,
<IMG  ALIGN=MIDDLE ALT="" SRC="img4.gif">, <IMG  ALIGN=MIDDLE ALT="" SRC="img5.gif">, 
and the function <IMG  ALIGN=BOTTOM ALT="" SRC="img6.gif"> consists of only these rules:
<P><IMG  ALIGN=BOTTOM ALT="" SRC="img7.gif"><P>
<P>
<LI> 
Here's a Turing machine that accepts <IMG  ALIGN=MIDDLE ALT="" SRC="img8.gif">:
<br>
<IMG SRC="hw10tm.gif">
<p>
Here's a brief description of <em> all</em> the states:
<UL><LI> <IMG  ALIGN=MIDDLE ALT="" SRC="img9.gif">: Read the first blank.
<LI> <IMG  ALIGN=MIDDLE ALT="" SRC="img10.gif">: This is the start of the match loop.  It looks for an <b>a</b> 
or a <b>b</b>.  If it sees a <b>c</b>, then we're done matching the first string.
<LI> <IMG  ALIGN=MIDDLE ALT="" SRC="img11.gif">: We've read a <b>b</b> and we're looking for the <b>c</b>.
<LI> <IMG  ALIGN=MIDDLE ALT="" SRC="img12.gif">: We've read an <b>a</b> and we're looking for the <b>c</b>.
<LI> <IMG  ALIGN=MIDDLE ALT="" SRC="img13.gif">: we're trying to match the <b>b</b>.
<LI> <IMG  ALIGN=MIDDLE ALT="" SRC="img14.gif">: we're trying to match the <b>a</b>.
<LI> <IMG  ALIGN=MIDDLE ALT="" SRC="img15.gif">: Scan left for the <b>c</b>.
<LI> <IMG  ALIGN=MIDDLE ALT="" SRC="img16.gif">: Scan left for the next thing to match in the first string.
<LI> <IMG  ALIGN=MIDDLE ALT="" SRC="img17.gif">: Verify that there is no other input in the second string.
<LI> <IMG  ALIGN=MIDDLE ALT="" SRC="img18.gif">: We've matched everything in the first string and found 
nothing else in the second string, so accept the input.
</UL>
Its computation of the input <b>abcab</b>:
<P><IMG  ALIGN=BOTTOM ALT="" SRC="img19.gif"><P>
<P>
<LI>
Let <IMG  ALIGN=MIDDLE ALT="" SRC="img20.gif">.  Assume all the productions in <b>P</b>, not of the form
<IMG  ALIGN=BOTTOM ALT="" SRC="img21.gif">, are numbered 1 to <b>m</b>.
<P>
The PDA <IMG  ALIGN=MIDDLE ALT="" SRC="img22.gif"> will accept
the language generated by <b>G</b>.  We need to specify <b>Q</b> and <IMG  ALIGN=BOTTOM ALT="" SRC="img23.gif">.
<P><IMG  ALIGN=BOTTOM ALT="" SRC="img24.gif"><P>
The function <IMG  ALIGN=BOTTOM ALT="" SRC="img25.gif"> consists of the following rules:
<P><IMG  ALIGN=BOTTOM ALT="" SRC="img26.gif"><P></OL><BR> <HR>
<UL> 
<LI> <A NAME=tex2html3 HREF="node1.html#SECTION00010000000000000000">   About this document ... </A>
</UL>
<BR> <HR>
<P><ADDRESS>
<I>James Fix <BR>
Tue Mar 12 08:07:49 PST 1996</I>
</ADDRESS>
</BODY>
